//#include<bits/stdc++.h>
//using namespace std;
//int cnt = 0;
//int queen[13][13] = {0};
//
//void doAdd(int r, int c, int n, int val)//添加标记
//{
//	if (r < 0 || r >= n) { // 行出界
//		return ;
//	}
//	if (c < 0 || c >= n) { // 列出界
//		return ;
//	}
//	queen[r][c] += val;// 1为加子 -1为提子
//}
//void add(int r, int c, int n, int val)// 执子操作
//{
//	int i ;
//	for (i = 0; i < n; i++) {
//		doAdd(r, i, n, val);// 标记所在行
//		doAdd(i, c, n, val);// 标记所在列
//	}
//	for (int i = 0; i < n; i++) {
//		// 主对角线
//		doAdd(r + i, c + i, n, val);
//		doAdd(r - i, c - i, n, val);
//		// 副对角线
//		doAdd(r + i, c - i, n, val);
//		doAdd(r - i, c + i, n, val);
//	}
//}
//void dfs(int depth, int maxDepth)// dfs 深度搜索
//{
//	int i;
//	if (depth == maxDepth) {// 到达最深就返回空
//		++cnt;// 次数 +1
//		cout << endl;
//		return ;
//	}
//	for (i = 0; i < maxDepth; i++) {// 向下搜索
//		if (queen[depth][i] == 0) {// 判断当前点是否可以放棋子
//			cout << i << " ";
//			add(depth, i, maxDepth, 1);// 加入棋盘
//			dfs(depth + 1, maxDepth);// 深度加一
//			add(depth, i, maxDepth, -1); // 取出
//
//		}
//	}
//}
//int main()
//{
//	int n;
//	cin >> n;
////	memset(queen, 0, sizeof(queen));
//	dfs(0, n);
//
//	cout << cnt;
//	return 0;
//}
//#include <iostream>
//#include <vector>
//using namespace std;
//
//// 检查当前位置是否可以放置一个棋子
//bool isValid(vector<int>& board, int row, int col)
//{
//	for (int i = 0; i < row; i++) {
//		// 检查是否在同一列或者对角线上
//		if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
//			return false;
//		}
//	}
//	return true;
//}
//
//// 递归地解决N皇后问题
//void solveNQueens(vector<vector<int>>& solutions, vector<int>& board, int row, int n, int& count)
//{
//	// 找到一个解，将其添加到结果集中
//	if (row == n) {
//		solutions.push_back(board);
//		count++;
//		return;
//	}
//
//	// 尝试放置棋子
//	for (int col = 0; col < n; col++) {
//		if (isValid(board, row, col)) {
//			board[row] = col; // 在当前行的col列放置一个棋子
//			solveNQueens(solutions, board, row + 1, n, count); // 递归处理下一行
//			board[row] = -1; // 回溯，将当前位置重置为-1
//		}
//	}
//}
//
//int main()
//{
//	int n;
//	cin >> n;
//
//	vector<vector<int>> solutions;//存储结果
//	//用一维数组表示二位
//	vector<int> board(n, -1); // 初始化棋盘，所有位置的值都为-1
//	int count = 0;
//
//	solveNQueens(solutions, board, 0, n, count);
//
//	// 输出前三个解
//	for (int i = 0; i < min(3, (int)solutions.size()); i++) {
//		for (int j = 0; j < n; j++) {
//			cout << solutions[i][j] + 1 << " "; // 将值加1后输出
//		}
//		cout << endl;
//	}
//
//	cout << solutions.size() << endl; // 输出解的总数
//
//	return 0;
//}
//// 1TLE
#include <iostream>
#include <vector>
using namespace std;

void backtrack(int row, int n, int cols, int diag1, int diag2, vector<int>& queens, vector<vector<int>>& result) {
	if (row == n) { // 如果已经放置完所有皇后，则找到了一个解
		result.push_back(queens);
		return;
	}
	
	int availablePositions = ((1 << n) - 1) & (~(cols | diag1 | diag2)); // 可用的位置是当前列、左上对角线和右上对角线均没有皇后的位置
	while (availablePositions != 0) { // 对所有可用的位置进行遍历
		int position = availablePositions & (-availablePositions); // 获取最低位的1，即可放置皇后的位置
		availablePositions &= (availablePositions - 1); // 清除最低位的1，将该位置标记为已使用
		
		int col_num = __builtin_ctz(position); // 获取位置的列数
		
		queens[row] = col_num; // 将皇后放置在该位置
		// 更新列、对角线的状态，并继续递归放置下一行的皇后
		backtrack(row + 1, n, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1, queens, result);
	}
}

vector<vector<int>> solveNQueens(int n) {
	vector<vector<int>> result;
	vector<int> queens(n, 0); // 用于存储每行皇后所在的列数
	
	backtrack(0, n, 0, 0, 0, queens, result); // 从第0行开始放置皇后
	
	return result;
}

int main() {
	int n;
	cin >> n; // 输入棋盘的大小
	
	vector<vector<int>> solutions = solveNQueens(n); // 求解所有解
	int count = solutions.size(); // 解的总个数
	
	// 输出前三个解
	for (int i = 0; i < min(3, count); i++) {
		for (int j = 0; j < n; j++) {
			cout << solutions[i][j] + 1 << " "; // 将列数加1输出，表示皇后所在的列
		}
		cout << endl;
	}
	
	cout << count << endl; // 输出解的总个数
	
	return 0;
}
// AC 位运算
